MacHack 1999/MacHack 1999.toast/Papers/atomicity/Code/atomicity.h

C/C++ Source or Header | 1999-06-25 | 19.3 KB | 646 lines | [TEXT/CWIE]

/****************************************************************************************
    atomicity.h

        The grabbing hands
            grab all they can.
        Everything counts
            in large amounts.

    Copyright © 1998-1999 Red Shed Software. All rights reserved.
    by Jonathan 'Wolf' Rentzsch ([e-mail])
    This code requires a 68020 or later or any PowerPC.

    Commenter    Date                Comment
    ---------    -----------------    -----------------------------------------------------
    wolf        Mon, Oct 26, 1998    Created as AtomicStacks.h/AtomicStacks.c.
    wolf        Mon, Nov 9, 1998    PowerPC code rolled in.
    wolf        Wed, Nov 18, 1998    Rolled in AtomicQueue code.

                                    Renamed to AtomicLists.h/AtomicLists.c.
    wolf        Mon, Nov 23, 1998    Added guarded lists code.
    wolf        Wed, Nov 25, 1998    Added ___Off functions and ___Type macros.

                                    Reworked file to be more comprehensible &
                                    navigatible.
    wolf        Mon, Nov 30, 1998    PushGuardedAtomicStack() was modified to be atomic.
    wolf        Wed, Dec 2, 1998    Added requirement checking.
    wolf        Thu, Dec 24, 1998    Added StealGuardedAtomicStackType() macro.
    wolf        Tue, Mar 23, 1999    Added conditionally compiled 'extern "C" {}'
                                    declaration.
    wolf        Mon, Mar 29, 1999    Added Open Transport compatibility options.

                                    Now uses size_t and offsetof() instead of long and
                                    my offof() macro, respectively.

                                    Renamed to atomicity.h/atomicity.c.
    wolf        Wed, Mar 31, 1999    Reworked OpenTransport compatibility & documented it.

                                    Added AtomicLocks.

                                    Now can stand without require.h (just comment it out
                                    in atomicity.c).

                                    The new public AtomicLocks code obsoleted my private
                                    IncrementGuardedAtomicStack() function, so the
                                    function has been removed and the Guarded Stack (and
                                    thus the Guarded Queue) code has been moved to Atomic
                                    Locks.
    wolf        Thu, Apr 15, 1999    Added Peek[Guarded]AtomicQueue[Off|Type]().
    wolf        Thu, Apr 22, 1999    Moved the OpenTransport compatibility settings into
                                    their own file: atomicity.config.h.
    wolf        Fri, Apr 30, 1999    Added Peek[Guarded]AtomicStack[Off|Type].
    wolf        Mon, May 3, 1999    Changed name of AtomicQueue's fields from (pushed,
                                    toPop) to (input, output) to ease understanding.

                                    Rearranged the parameter order of the ___Off and
                                    ___Type functions. Before it was ( OFFSET, STACK )
                                    and ( STRUCTURE, FIELD, STACK ). Now it's
                                    ( STACK, OFFSET ) and ( STACK, STRUCTURE, FIELD ).
                                    This breaks existing code, but the fix is simple and
                                    the new way is easier to remember. I wanted to make
                                    this change before I distributed my code on the
                                    MacHack 99 CD-ROM.
    wolf        Fri, May 7, 1999    The Open Transport Compatibility Options weren't
                                    working correctly for some reason (apparently my
                                    concepts about what !defined() means is wrong).
                                    I reworked it a little and now all is well.

                                    Added (OpenAtomicity(), CloseAtomicity()) macros
                                    that call thru to (InitOpenTransport(),
                                    CloseOpenTransport()) as needed depending on the
                                    settings in atomicity.config.h.

    ************************************************************************************/

#ifndef        _atomicity_
#define        _atomicity_

#include    <stddef.h>
#include    "atomicity.config.h"
#include    "extern_c.h"

begin_extern_c

/****************************************************************************************
*
*    Atomic Stacks
*
****************************************************************************************/
#pragma mark    --Atomic Stacks--

typedef    struct    AtomicElement    AtomicElement, AtomicStack;

struct    AtomicElement    {
    AtomicElement    *next;

#ifdef    __cplusplus
    AtomicElement() : next( nil ){}
#endif
};

/**************************
*
*    Atomic Stack Functions
*
*    An atomic stack is an atomic last-in-first-out list.
*
*    These are the lowest level functions to atomically manipulate stacks.
*
**************************/
#pragma mark    --Atomic Stack Functions--

//    Atomically set element->next to stack->next, set stack->next to element.

    extern
    pascal
    void
MyPushAtomicStack(
    AtomicElement    *element,
    AtomicStack        *stack );

//    Atomically store stack->next, set stack->next to stack->next->next, and return the
//    first element. It's okay if stack->next == nil: PopAtomicStack() will return nil.

    extern
    pascal
    AtomicElement*
MyPopAtomicStack(
    AtomicStack        *stack );

//    Atomically store stack->next, set stack->next to nil, and return the
//    first element. It's okay if stack->next == nil: StealAtomicStack() will return nil.

    extern
    pascal
    AtomicElement*
MyStealAtomicStack(
    AtomicStack        *stack );

//    Simply returns stack->next.

    extern
    pascal
    AtomicElement*
PeekAtomicStack(
    AtomicStack        *stack );

/**************************
*
*    Atomic Stack Offset Functions
*
*    Convenience routines for when the AtomicElement field in your structure
*    can't be the first field. You supply the coercions and field offset.
*
**************************/
#pragma mark    --Atomic Stack Offset Functions--

//    Adds offset to element, and calls PushAtomicStack().

    extern
    pascal
    void
PushAtomicStackOff(
    void            *element,
    AtomicStack        *stack,
    size_t            offset );

//    Calls PopAtomicStack(), if the result is not nil, subtracts offset from the result
//    and returns it.

    extern
    pascal
    AtomicElement*
PopAtomicStackOff(
    AtomicStack        *stack,
    size_t            offset );

//    Calls StealAtomicStack(), if the result is not nil, subtracts offset from the result
//    and returns it.

    extern
    pascal
    AtomicElement*
StealAtomicStackOff(
    AtomicStack        *stack,
    size_t            offset );

//    Calls PeekAtomicStack(), if the result is not nil, subtracts offset from the result
//    and returns it.

    extern
    pascal
    AtomicElement*
PeekAtomicStackOff(
    AtomicStack        *stack,
    size_t            offset );

/**************************
*
*    Atomic Stack Type Functions
*
*    Convenience routines for when the AtomicElement field in your structure
*    can't be the first field. You supply the structure and field names. It does
*    the coercions and offsets for you.
*
**************************/
#pragma mark    --Atomic Stack Type Functions--

#define        PushAtomicStackType( ELEMENT, STACK, STRUCTURE, FIELD )    \
                PushAtomicStackOff( (ELEMENT), (STACK), offsetof( STRUCTURE, FIELD ) )

#define        PopAtomicStackType( STACK, STRUCTURE, FIELD )    \
                ((STRUCTURE*) PopAtomicStackOff( (STACK), offsetof( STRUCTURE, FIELD ) ))

#define        StealAtomicStackType( STACK, STRUCTURE, FIELD )    \
                ((STRUCTURE*) StealAtomicStackOff( (STACK), offsetof( STRUCTURE, FIELD ) ))

#define        PeekAtomicStackType( STACK, STRUCTURE, FIELD )    \
                ((STRUCTURE*) PeekAtomicStackOff( (STACK), offsetof( STRUCTURE, FIELD ) ))

/****************************************************************************************
*
*    AtomicLock
*
****************************************************************************************/
#pragma mark    -
#pragma mark    --Atomic Locks--

typedef    unsigned    long    AtomicLock;

    extern
    pascal
    long    //    Non-zero if successfully grabbed.
MyGrabAtomicLock(
    AtomicLock    *lock );

    extern
    void
ReleaseAtomicLock(
    AtomicLock    *lock );

/****************************************************************************************
    Open Transport Compatibility Options

    Define DontUseOpenTransport *or* UseOpenTransportIfAvailable *or*
    OnlyUseOpenTransport in the file atomicity.config.h. If you don't define any of
    these, the default is UseOpenTransportIfAvailable.

    If you define UseOpenTransportIfAvailable or OnlyUseOpenTransport, you *must* call
    InitOpenTransport() in the beginning of your application. If you don't want to
    juggle whether or not to call InitOpenTransport(), simply always call
    OpenAtomicity(). If you defined UseOpenTransportIfAvailable or OnlyUseOpenTransport,
    it maps to InitOpenTransport(), otherwise it maps to noErr.

    DontUseOpenTransport:
        o    Open Transport Libraries: Not Required.
        o    Runtime Overhead: None.

    UseOpenTransportIfAvailable:
        o    Open Transport Libraries: Required (preferably weakly imported).
        o    Runtime Overhead: Small (larger if requirements checking is turned on).

    OnlyUseOpenTransport:
        o    Open Transport Libraries: Required (preferably strongly imported).
        o    Runtime Overhead: None.

    ************************************************************************************/
#pragma mark    -
#pragma mark    --Open Transport Compatibility Options--

#if        defined(DontUseOpenTransport)
    #define    PushAtomicStack( ELEMENT, STACK )    MyPushAtomicStack( ELEMENT, STACK )
    #define    PopAtomicStack( STACK )                MyPopAtomicStack( STACK )
    #define    StealAtomicStack( STACK )            MyStealAtomicStack( STACK )
    #define    GrabAtomicLock( LOCK )                MyGrabAtomicLock( LOCK )
    #define    OpenAtomicity()                        noErr
    #define    CloseAtomicity()
#elif    defined(OnlyUseOpenTransport)
    #include    "OpenTransport.h"
    #define    PushAtomicStack( ELEMENT, STACK )    OTLIFOEnqueue( (OTLIFO*) STACK, (OTLink*) ELEMENT )
    #define    PopAtomicStack( STACK )                (AtomicElement*) OTLIFODequeue( (OTLIFO*) STACK )
    #define    StealAtomicStack( STACK )            (AtomicElement*) OTLIFOStealList( (OTLIFO*) STACK )
    #define    GrabAtomicLock( LOCK )                OTCompareAndSwap32( 0, 1, LOCK )
    #define    OpenAtomicity()                        InitOpenTransport()
    #define    CloseAtomicity()                    CloseOpenTransport()
#else    //    UseOpenTransportIfAvailable
    #include    "OpenTransport.h"
    extern    void                                PushAtomicStack( AtomicElement *element, AtomicStack *stack );
    extern    AtomicElement*                         PopAtomicStack( AtomicStack *stack );
    extern    AtomicElement*                         StealAtomicStack( AtomicStack *stack );
    extern    Boolean                                GrabAtomicLock( AtomicLock *lock );
    #define    OpenAtomicity()                        InitOpenTransport()
    #define    CloseAtomicity()                    CloseOpenTransport()
#endif

/****************************************************************************************
*
*    Guarded Atomic Stacks
*
****************************************************************************************/
#pragma mark    -
#pragma mark    --Guarded Atomic Stacks--

typedef    struct    GuardedAtomicElement    GuardedAtomicElement;

struct    GuardedAtomicElement    {
    GuardedAtomicElement    *next;
    AtomicLock                lock;

#ifdef    __cplusplus
    GuardedAtomicElement() : next( nil ), lock( 0 ){}
#endif
};

/**************************
*
*    Guarded Atomic Stack Functions
*
*    A guarded atomic stack doesn't allow an element to be pushed more than once.
*    Pushing an element more than once on a stack corrupts the stack into a nasty
*    circular list. These functions test whether the element in already on a stack
*    before blindly pushing the element, saving your stack from corruption.
*
**************************/
#pragma mark    --Guarded Atomic Stack Functions--

//    Call GrabAtomicLock() on element->lock. If successful, call PushAtomicStack() and
//    return true. Otherwise return false.

    extern
    pascal
    long
PushGuardedAtomicStack(
    GuardedAtomicElement    *element,
    AtomicStack                *stack );

//    Call PopAtomicStack(). If the result isn't nil, call ReleaseAtomicLock() on the popped
//    element->lock and return the popped element. Otherwise return nil.

    extern
    pascal
    GuardedAtomicElement*
PopGuardedAtomicStack(
    AtomicStack                *stack );

//    Simply returns stack->next.

    extern
    pascal
    GuardedAtomicElement*
PeekGuardedAtomicStack(
    AtomicStack                *stack );

#define        StealGuardedAtomicStack( STACK )    StealAtomicStack( STACK )

/**************************
*
*    Guarded Atomic Stack Offset Functions
*
*    Convenience routines for when the GuardedAtomicElement field in your structure
*    can't be the first field. You supply the coercions and field offset.
*
**************************/
#pragma mark    --Guarded Atomic Stack Offset Functions--

//    Adds offset to element, and calls PushGuardedAtomicStack().

    extern
    pascal
    long
PushGuardedAtomicStackOff(
    void            *element,
    AtomicStack        *stack,
    size_t            offset );

//    Calls PopGuardedAtomicStack(), if the result is not nil, subtracts offset from
//    the result and returns it.

    extern
    pascal
    GuardedAtomicElement*
PopGuardedAtomicStackOff(
    AtomicStack        *stack,
    size_t            offset );

//    Calls PeekGuardedAtomicStack(), if the result is not nil, subtracts offset from
//    the result and returns it.

    extern
    pascal
    GuardedAtomicElement*
PeekGuardedAtomicStackOff(
    AtomicStack        *stack,
    size_t            offset );

#define        StealGuardedAtomicStackOff( STACK, OFF )    StealAtomicStackOff( STACK, OFF )

/**************************
*
*    Guarded Atomic Stack Type Functions
*
*    Convenience routines for when the GuardedAtomicElement field in your structure
*    can't be the first field. You supply the structure and field names. It does
*    the coercions and offsets for you.
*
**************************/
#pragma mark    --Guarded Atomic Stack Type Functions--

#define        PushGuardedAtomicStackType( ELEMENT, STACK, STRUCTURE, FIELD )    \
                PushGuardedAtomicStackOff( (ELEMENT), (STACK), offsetof( STRUCTURE, FIELD ) )

#define        PopGuardedAtomicStackType( STACK, STRUCTURE, FIELD )    \
                ((STRUCTURE*) PopGuardedAtomicStackOff( (STACK), offsetof( STRUCTURE, FIELD ) ))

#define        StealGuardedAtomicStackType( STACK, STRUCTURE, FIELD )    \
                ((STRUCTURE*) StealGuardedAtomicStackOff( (STACK), offsetof( STRUCTURE, FIELD ) ))

#define        PeekGuardedAtomicStackType( STACK, STRUCTURE, FIELD )    \
                ((STRUCTURE*) PeekAtomicStackOff( (STACK), offsetof( STRUCTURE, FIELD ) ))

/****************************************************************************************
*
*    Atomic Queues
*
****************************************************************************************/
#pragma mark    -
#pragma mark    --Atomic Queues--

typedef    struct    {
    AtomicStack        input;
    AtomicStack        output;
}    AtomicQueue;

/**************************
*
*    Atomic Queue Functions
*
*    An atomic queue is an atomic first-in-first-out list.
*
**************************/
#pragma mark    --Atomic Queue Functions--

//    Simply calls PushAtomicStack() with queue->input.

    extern
    pascal
    void
PushAtomicQueue(
    AtomicElement    *element,
    AtomicQueue        *queue );

//    Calls PopAtomicStack() with queue->output. If the result is not nil,
//    PopAtomicQueue() returns it. Otherwise PopAtomicQueue() calls
//    StealAtomicList() on queue->input. If the result is not nil,
//    PopAtomicQueue() calls PopAtomicStack() on each element in the stolen stack,
//    then calling PushAtomicStack() with queue->output, effectively "reversing" the
//    stack into a queue.

    extern
    pascal
    AtomicElement*
PopAtomicQueue(
    AtomicQueue        *queue );

//    Calls PopAtomicQueue(). If the result is not nil, then it calls PushAtomicStack()
//    with the result on queue->output.

    extern
    pascal
    AtomicElement*
PeekAtomicQueue(
    AtomicQueue        *queue );

/**************************
*
*    Atomic Queue Offset Functions
*
*    Convenience routines for when the AtomicElement field in your structure
*    can't be the first field. You supply the coercions and field offset.
*
**************************/
#pragma mark    --Atomic Queue Offset Functions--

//    Adds offset to element, and calls PushAtomicQueue().

    extern
    pascal
    void
PushAtomicQueueOff(
    void            *element,
    AtomicQueue        *queue,
    size_t            offset );

//    Calls PopAtomicQueue(), if the result is not nil, subtracts offset from
//    the result and returns it.

    extern
    pascal
    AtomicElement*
PopAtomicQueueOff(
    AtomicQueue        *queue,
    size_t            offset );

//    Calls PeekAtomicStack(). If the result is not nil, subtracts offset from
//    the result and returns it.

    extern
    pascal
    AtomicElement*
PeekAtomicQueueOff(
    AtomicQueue        *queue,
    size_t            offset );

/**************************
*
*    Atomic Queue Type Functions
*
*    Convenience routines for when the AtomicElement field in your structure
*    can't be the first field. You supply the structure and field names. It does
*    the coercions and offsets for you.
*
**************************/
#pragma mark    --Atomic Queue Type Functions--

#define        PushAtomicQueueType( ELEMENT, QUEUE, STRUCTURE, FIELD )    \
                PushAtomicQueueOff( (ELEMENT), (QUEUE), offsetof( STRUCTURE, FIELD ) )

#define        PopAtomicQueueType( QUEUE, STRUCTURE, FIELD )    \
                ((STRUCTURE*) PopAtomicQueueOff( (QUEUE), offsetof( STRUCTURE, FIELD ) ))

#define        PeekAtomicQueueType( QUEUE, STRUCTURE, FIELD )    \
                ((STRUCTURE*) PeekAtomicQueueOff( (QUEUE), offsetof( STRUCTURE, FIELD ) ))

/****************************************************************************************
*
*    Guarded Atomic Queues
*
****************************************************************************************/
#pragma mark    -
#pragma mark    --Guarded Atomic Queues--

/**************************
*
*    Guarded Atomic Queue Functions
*
*    A guarded atomic queue is an atomic queue that doesn't allow an element to be
*    pushed more than once.
*
**************************/
#pragma mark    --Guarded Atomic Queue Functions--

//    Simply calls PushGuardedAtomicStack() with queue->input.

    extern
    pascal
    long
PushGuardedAtomicQueue(
    GuardedAtomicElement    *element,
    AtomicQueue                *queue );

//    Calls PopGuardedAtomicStack() with queue->output. If the result is not nil,
//    PopGuardedAtomicQueue() returns it. Otherwise PopGuardedAtomicQueue() calls
//    StealAtomicList() on queue->input. If the result is not nil,
//    PopGuardedAtomicQueue() calls PopAtomicStack() on each element in the stolen stack,
//    then calling PushAtomicStack() with queue->output, effectively "reversing" the
//    stack into a queue.

    extern
    pascal
    GuardedAtomicElement*
PopGuardedAtomicQueue(
    AtomicQueue        *queue );

//    If queue->output.next is nil, then PeekGuardedAtomicQueue() calls
//    StealAtomicList() on queue->input. If the result is not nil,
//    PopGuardedAtomicQueue() calls PopAtomicStack() on each element in the stolen stack,
//    then calling PushAtomicStack() with queue->output, effectively "reversing" the
//    stack into a queue. PeekGuardedAtomicQueue() returns queue->output.next.

    extern
    pascal
    GuardedAtomicElement*
PeekGuardedAtomicQueue(
    AtomicQueue        *queue );

/**************************
*
*    Guarded Atomic Queue Offset Functions
*
*    Convenience routines for when the AtomicElement field in your structure
*    can't be the first field. You supply the coercions and field offset.
*
**************************/
#pragma mark    --Guarded Atomic Queue Offset Functions--

//    Adds offset to element, and calls PushGuardedAtomicQueue().

    extern
    pascal
    long
PushGuardedAtomicQueueOff(
    void            *element,
    AtomicQueue        *queue,
    size_t            offset );

//    Calls PopGuardedAtomicQueue(), if the result is not nil, subtracts offset from
//    the result and returns it.

    extern
    pascal
    GuardedAtomicElement*
PopGuardedAtomicQueueOff(
    AtomicQueue        *queue,
    size_t            offset );

//    Calls PekkGuardedAtomicQueue(), if the result is not nil, subtracts offset from
//    the result and returns it.

    extern
    pascal
    GuardedAtomicElement*
PeekGuardedAtomicQueueOff(
    AtomicQueue        *queue,
    size_t            offset );

/**************************
*
*    Guarded Atomic Queue Type Functions
*
*    Convenience routines for when the AtomicElement field in your structure
*    can't be the first field. You supply the structure and field names. It does
*    the coercions and offsets for you.
*
**************************/
#pragma mark    --Guarded Atomic Queue Type Functions--

#define        PushGuardedAtomicQueueType( ELEMENT, QUEUE, STRUCTURE, FIELD )    \
                PushGuardedAtomicQueueOff( (ELEMENT), (QUEUE), offsetof( STRUCTURE, FIELD ) )

#define        PopGuardedAtomicQueueType( QUEUE, STRUCTURE, FIELD )    \
                ((STRUCTURE*) PopGuardedAtomicQueueOff( (QUEUE), offsetof( STRUCTURE, FIELD ) ))

#define        PeekGuardedAtomicQueueType( QUEUE, STRUCTURE, FIELD )    \
                ((STRUCTURE*) PeekGuardedAtomicQueueOff( (QUEUE), offsetof( STRUCTURE, FIELD ) ))

end_extern_c
#endif    //    _atomicity_